package leetcode100;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode add(int v, ListNode head) {
        ListNode node = new ListNode(v);
        node.next = head;
        return node;
    }


    public void visit() {
        ListNode node = this;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}


public class lc003 {

    public static void main(String[] args) {
        //  A   1 4 8 4 5
        //  B 5 6 1 8 4 5
        ListNode headA = new ListNode(5);
        headA = headA.add(4, headA);
        headA = headA.add(8, headA);

        ListNode headB = new ListNode(1);
        headB.next = headA;
        headB = headB.add(6, headB);
        headB = headB.add(5, headB);
        headA = headA.add(1, headA);
        headA = headA.add(4, headA);

        headA.visit();
        headB.visit();

        ListNode res = getIntersectionNode(headA, headB);
        System.out.println(res.val);
        res.visit();
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur = headA;
        int countA = 0;
        int countB = 0;
        while (cur != null) {
            countA++;
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            countB++;
            cur = cur.next;
        }
        cur = null;
        ListNode curA = headA;
        ListNode curB = headB;
        if (countA > countB) {
            for (int i = 0; i < countA - countB; i++) {
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < countB - countA; i++) {
                curB = curB.next;
            }
        }

        while (curA != null && curB != null) {
            if (curA == curB) return curA;
            curA = curA.next;
            curB = curB.next;
        }


        return null;
    }


}
